C++ 18：C++ 标准库常用算法

课程目标

了解 C++ algorithm 库的基本概念
熟悉常见的算法函数及其用途
通过实际代码示例掌握算法的使用方法

课程内容

引言与简介 (5 分钟)
常用的非修改算法 (20 分钟)
- std::all_of
- std::any_of
- std::none_of
- std::for_each
常用的修改算法 (20 分钟)
- std::transform
- std::copy
- std::replace
- std::fill
数值算法 (15 分钟)
- std::accumulate
- std::iota
排序算法 (30 分钟)
- std::sort
- std::stable_sort
- std::partial_sort
- std::nth_element
查找算法 (15 分钟)
- std::find
- std::binary_search
- std::equal_range
总结与习题 (15 分钟)

1. 引言与简介 1

什么是 `algorithm` 库？

algorithm 是 C++ 标准库中一个非常重要的模块，提供了一些非常常见且高效的数据处理函数。
这些算法涵盖了各种数据处理操作，如查找、排序、复制、修改等。

2. 常用的非修改算法 4

2.1 `std::all_of`

std::all_of 检查范围内的所有元素是否都满足一个给定的条件。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {2, 4, 6, 8, 10};

    bool all_even = std::all_of(vec.begin(), vec.end(), [](int i){ return i % 2 == 0; });

    std::cout << (all_even ? "All elements are even" : "Not all elements are even") << std::endl;

    return 0;
}

2.2 `std::any_of`

std::any_of 检查范围内是否至少有一个元素满足一个给定的条件。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 3, 5, 7, 8};

    bool has_even = std::any_of(vec.begin(), vec.end(), [](int i){ return i % 2 == 0; });

    std::cout << (has_even ? "There is at least one even element" : "All elements are odd") << std::endl;

    return 0;
}

2.3 `std::none_of`

std::none_of 检查范围内的所有元素是否都不满足一个给定的条件。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 3, 5, 7};

    bool none_even = std::none_of(vec.begin(), vec.end(), [](int i){ return i % 2 == 0; });

    std::cout << (none_even ? "None of the elements are even" : "There is at least one even element") << std::endl;

    return 0;
}

2.4 `std::for_each`

std::for_each 对范围内的每个元素执行给定的操作。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    std::for_each(vec.begin(), vec.end(), [](int &n){ n *= 2; });

    for (const auto& n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 常用的修改算法 4

3.1 `std::transform`

std::transform 使用给定的操作将范围内的元素应用到输出范围，常用来实现元素整体的转换。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> result(vec.size());

    std::transform(vec.begin(), vec.end(), result.begin(), [](int v){ return v * v; });

    for (const auto& v : result) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2 `std::copy`

std::copy 将一个范围的元素复制到另一个范围。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination(source.size());

    std::copy(source.begin(), source.end(), destination.begin());

    for (const auto& v : destination) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.3 `std::replace`

std::replace 将指定范围内的所有等于某个值的元素替换为新值。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

    std::replace(vec.begin(), vec.end(), 2, 10);

    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.4 `std::fill`

std::fill 用一个特定值替代范围内的所有元素。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec(5);

    std::fill(vec.begin(), vec.end(), 7);

    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. 数值算法 3

4.1 `std::accumulate`

std::accumulate 用于对范围内的元素进行累加。

示例代码：

cpp

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    int sum = std::accumulate(vec.begin(), vec.end(), 0);

    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

4.2 `std::iota`

std::iota 用于给定范围填充连续递增的值。

示例代码：

cpp

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec(5);

    std::iota(vec.begin(), vec.end(), 1);

    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

5. 排序算法 6

5.1 `std::sort`

std::sort 对给定范围进行排序。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2};

    std::sort(vec.begin(), vec.end());

    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

好的，继续讲解剩下的内容：

5.2 `std::stable_sort`

std::stable_sort 类似于 std::sort，但它是稳定排序，意味着在相等元素间保持相对顺序。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

struct Person {
    std::string name;
    int age;
};

bool compare_by_age(const Person& a, const Person& b) {
    return a.age < b.age;
}

int main() {
    std::vector<Person> people = { {"Alice", 30}, {"Bob", 20}, {"Charlie", 30}, {"Dave", 20} };

    std::stable_sort(people.begin(), people.end(), compare_by_age);

    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }

    return 0;
}

5.3 `std::partial_sort`

std::partial_sort 对部分元素进行排序，保证前 n 个元素是最小的 n 个，并按顺序排列。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {9, 3, 7, 1, 3, 6, 5, 8, 2, 4};

    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());

    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

5.4 `std::nth_element`

std::nth_element 重排范围使得第 n 个元素在它应处的地方，前面的元素均不大于它，后面的元素均不小于它。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {9, 1, 8, 3, 7, 2, 6, 4, 5};

    std::nth_element(vec.begin(), vec.begin() + 4, vec.end());

    std::cout << "Element at index 4: " << vec[4] << std::endl;

    std::cout << "Array after nth_element: ";
    for (const auto& v : vec) {
        std::cout << v << " ";
    }
    std::cout << std::endl;

    return 0;
}

6. 查找算法 3

6.1 `std::find`

std::find 在指定范围内寻找第一个等于指定值的元素。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};

    auto it = std::find(vec.begin(), vec.end(), 4);

    if (it != vec.end()) {
        std::cout << "Element found at position: " << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

6.2 `std::binary_search`

std::binary_search 在有序范围内快速检查是否存在某个值。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};

    bool found = std::binary_search(vec.begin(), vec.end(), 4);

    std::cout << (found ? "Element found" : "Element not found") << std::endl;

    return 0;
}

6.3 `std::equal_range`

std::equal_range 在有序范围内返回第一个和最后一个等于某个值的元素的范围。

示例代码：

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 3, 3, 4, 5};

    auto range = std::equal_range(vec.begin(), vec.end(), 3);

    std::cout << "First occurrence of 3 at position: " << std::distance(vec.begin(), range.first) << std::endl;
    std::cout << "Last occurrence of 3 at position: " << std::distance(vec.begin(), range.second) - 1 << std::endl;

    return 0;
}

7. 总结与习题 3

总结

非修改算法：主要用于检查或处理数据，而不改变数据内容，如 std::all_of、std::find、std::for_each 等。
修改算法：直接改变元素内容或在新位置生成改变后的内容，如 std::transform、std::replace、std::fill 等。
数值算法：处理数值范围的算法，如 std::accumulate、std::iota。
排序与查找算法：提供标准的排序和查找方式，如 std::sort、std::stable_sort、std::find、std::binary_search 等。

作业：

给定一个整数列表 numbers，请你完成以下操作：

找出列表中的最小值和最大值分别输出。
计算总和以及平均值分别输出。
分别输出所有的奇数和偶数。
将列表中的每个数奇数加 5，偶数减5，并按升序排序输出.
numbers =

C++ 18：C++ 标准库常用算法 ​

课程目标 ​

课程内容 ​

1. 引言与简介 1 ​

什么是 algorithm 库？ ​

2. 常用的非修改算法 4 ​

2.1 std::all_of ​

2.2 std::any_of ​

2.3 std::none_of ​

2.4 std::for_each ​

3. 常用的修改算法 4 ​

3.1 std::transform ​

3.2 std::copy ​

3.3 std::replace ​

3.4 std::fill ​

4. 数值算法 3 ​

4.1 std::accumulate ​

4.2 std::iota ​

5. 排序算法 6 ​

5.1 std::sort ​

5.2 std::stable_sort ​

5.3 std::partial_sort ​

5.4 std::nth_element ​

6. 查找算法 3 ​

6.1 std::find ​

6.2 std::binary_search ​

6.3 std::equal_range ​

7. 总结与习题 3 ​

总结 ​

作业： ​

C++ 18：C++ 标准库常用算法

课程目标

课程内容

1. 引言与简介 1

什么是 `algorithm` 库？

2. 常用的非修改算法 4

2.1 `std::all_of`

2.2 `std::any_of`

2.3 `std::none_of`

2.4 `std::for_each`

3. 常用的修改算法 4

3.1 `std::transform`

3.2 `std::copy`

3.3 `std::replace`

3.4 `std::fill`

4. 数值算法 3

4.1 `std::accumulate`

4.2 `std::iota`

5. 排序算法 6

5.1 `std::sort`

5.2 `std::stable_sort`

5.3 `std::partial_sort`

5.4 `std::nth_element`

6. 查找算法 3

6.1 `std::find`

6.2 `std::binary_search`

6.3 `std::equal_range`

7. 总结与习题 3

总结

作业：